package com.leetcode;

/**
 * 279. 完全平方数
 * 动态规划
 *
 * @author fy
 * @date 2022/3/29 11:17
 */
public class Solution279 {

    public int numSquares(int n) {
        int[] count = new int[n + 1];
        count[0] = 0;
        count[1] = 1;
        for (int i = 2; i <= n; i++) {
            int minCount = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                int newCount = 1 + count[i - j * j];
                minCount = Math.min(newCount, minCount);
            }
            count[i] = minCount;
        }
        return count[n];
    }

    public static void main(String[] args) {
        System.out.println(new Solution279().numSquares(12));
    }

}
